package algorithm.middle;


import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Subsets78and90
 * @description: 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 *
 * 示例 2：
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subsets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/319:15
 * @since V1.0
 */

public class Subsets78and90 {


    //回溯 DFS 深度搜索
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        bfs(0,nums);
        return ans;
    }

    public void dfs(int i,int[] nums){
        if (i==nums.length){
            ans.add(new ArrayList<>(t));
            return;
        }
        t.add(nums[i]);
        dfs(i+1,nums);
        t.remove(t.size()-1);
        dfs(i+1,nums);
    }

    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    /**
     * 记原序列中元素的总数为 n。原序列中的每个数字 ai​ 的状态可能有两种，即「在子集中」和「不在子集中」。
     * 我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 ai​ 是否在子集中。
     *可以发现 0/1 序列对应的二进制数正好从 0 到2^n - 1。
     * 我们可以枚举 mask∈[0,2n−1]，mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/1序列在原集合当中取数
     * 。当我们枚举完所有 2^n个 mas，我们也就能构造出所有的子集。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public List<List<Integer>> 枚举(int[] nums) {
        //假如n为3
        int n = nums.length;
        //mask < 1000
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                //假设mask为011时
                //011 & 001 ; 011 & 010 ; 011 & 100
                //add(nums[0])  add(nums[1]) ===>  [1,2]
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }

    /**
     *90. 子集 II
     *
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     *
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,2]
     * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     *
     * 示例 2：
     *
     * 输入：nums = [0]
     * 输出：[[],[0]]
     */
    public List<List<Integer>> 枚举2(int[] nums) {
        Arrays.sort(nums);
        //假如n为3
        int n = nums.length;
        //mask < 1000
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            boolean flag = true;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    /**
                     * 考虑数组 [1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。
                     * 也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含x 的子集，必然会出现在包含 y的所有子集中。
                     * 我们可以通过判断这种情况，来避免生成重复的子集。代码实现时，可以先将数组排序；迭代时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
                     */
                    if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
                        flag = false;
                        break;
                    }
                    t.add(nums[i]);
                }
            }
            if(flag){
                ans.add(new ArrayList<Integer>(t));
            }
        }
        return ans;
    }

    /* 回溯 BFS 广度搜索
     * 比如说求 nums = [1,2,2] 的子集，那么对于子集 [1,2] 是选择了第一个 2，那么就不能再选第二个 2 来构成 [1,2] 了。
     * 所以，此时的改动点，就是先排序，每个元素 nums[i] 添加到 path 之前，判断一下 nums[i] 是否等于 nums[i - 1] ，如果相等就不添加到 path 中。
     */
    public void bfs(int i,int[] nums){
        ans.add(new ArrayList<>(t));
        for (int j=i;j<nums.length;j++){
            if (j>i &&  nums[j]==nums[j-1]){
                continue;
            }
            t.add(nums[j]);
            bfs(j+1,nums);
            t.remove(t.size()-1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> subsets = new Subsets78and90().subsets(new int[]{1, 2, 2});
        System.out.println(subsets);
    }
}
